package rong;

public class RBTree<T extends Comparable<T>> extends Tree<T, RBNode<T>> {
	
	private boolean rbStrict = true;
	
	public RBNode<T> add(T data) {
		if (root == null) {
			RBNode<T> x = new RBNode<T>();
			x.red = false;
			x.data = data;
			return root = x;
		}
		RBNode<T> node = searchAndAdd(root, data);
		if (rbStrict) {
			banlanceAdd(node);
		}
		return node;
	}
	
	public RBNode<T> delete(RBNode<T> x) {
		checkBelonging(x);
		if (x.left!=null && x.right!=null) {
			return null;
		}
		RBNode<T> replacement = null;
		if (x.left==null) {
			if (x.right==null) {
				replacement = null;
			} else {
				replacement = x.right;
			}
		} else {
			replacement = x.left;
		}
		if (x.parrent != null) {
			if (x.parrent.left==x) {
				x.parrent.left = replacement;
			} else {
				x.parrent.right = replacement;
			}
		} else {
			root = replacement;
		}
		if (replacement!=null) {
			replacement.parrent = x.parrent;
		}
		return replacement;
	}
	
	private void banlanceAdd(RBNode<T> x) {
		if (x.parrent == null) {
			x.red = false;
			return;
		} 
		x.red = true;
		RBNode<T> xp = x.parrent;
		if (!x.parrent.red) {
			return;
		}
		RBNode<T> xpp = xp.parrent;
		RBNode<T> xppl = xpp.left;
		RBNode<T> xppr = xpp.right;
		if (xp==xppl) {
			if (xppr !=null && xppr.red) {
				xppl.red = false;
				xppr.red = false;
				xpp.red = true;
				banlanceAdd(xpp);
			} else {
				if (x==xp.right) {
					rotateLeft(xp);
				}
				xpp.left.red = false;
				xpp.red = true;
				rotateRight(xpp);
			}
		} else {
			if (xppl !=null && xppl.red) {
				xppl.red = false;
				xppr.red = false;
				xpp.red = true;
				banlanceAdd(xpp);
			} else {
				if (x==xp.left) {
					rotateRight(xp);
				}
				xpp.right.red = false;
				xpp.red = true;
				rotateLeft(xpp);
			}
		}
	}
	
	private RBNode<T> searchAndAdd(RBNode<T> x, T data) {
		RBNode<T> node = null;
		if (x.data != null) {
			if (x.data.compareTo(data)>=0) {
				if (x.left !=null) {
					node = searchAndAdd(x.left, data);
				} else {
					node = new RBNode<T>();
					node.red = true;
					node.data = data;
					node.parrent = x;
					x.left = node;
				}
			} else {
				if (x.right !=null) {
					node = searchAndAdd(x.right, data);
				} else {
					node = new RBNode<T>();
					node.red = true;
					node.data = data;
					node.parrent = x;
					x.right = node;
				}
			}
		}
		return node;
	}
	
	public void checkRBTree() {
		if (!isRBTree()) {
			throw new RuntimeException(root + " is no Red Black Tree!");
		}
	}
	public boolean isRBTree() {
		if (root==null) {
			return true;
		}
		return blackLength(root) != -1;
	}
	
	private int blackLength(RBNode<T> x){
		if (x==null) {
			return 0;
		}
		int blenM = x.red?0:1;
		int blenL = blackLength(x.left);
		int blenR = blackLength(x.right);
		return (blenL == blenR)? (blenL + blenR + blenM) : -1;
	}
	
	public void reverseColor(RBNode<T> x) {
		if (!rbStrict) {
			checkBelonging(x);
			x.red = !x.red;
		}
	}
	
	public void setRBStrict(boolean rbStrict) {
		if (this.rbStrict == rbStrict) {
			return;
		}
		if (rbStrict) {
			checkRBTree();
		}
		this.rbStrict = rbStrict;
	}

}
